The present invention is directed to processes of interleaving input data from multiple asynchronous data streams into a single output data stream. Several applications require such interleaving of data, including satellite (i.e., telemetry) data and data from duplex document copying.
When two independent clocks are present in a system, there will always be an unknown phase relationship between the two clock sources. Furthermore, no matter what the clock sources are, there will also be a frequency difference. This frequency difference will cause the clocks to move in both time and phase relationship to each other. There are two cases to consider when analyzing this scenario as shown in FIG. 1 where Clock Source 2 is slower than Clock Source 1. The other scenario is illustrated in FIG. 2 where Clock Source 2 is faster than Clock Source 1. For discussion purposes, Clock Source 1 will be used as the reference clock source.
Although the frequency difference is overly exaggerated in FIG. 1 and FIG. 2, it can be seen from the initial coincident rising edge (t.sub.1) until the next coincident rising edge (t.sub.2) that there is a difference in the number of cycles that each clock goes through. The problem arises when a third system receives this data and is required to maintain a certain relationship between the data being received from both clock sources. In FIG. 1, the data stream associated with Clock Source 2 is falling behind the data stream associated with Clock Source 1. In FIG. 2 the opposite condition occurs. Thus, in any given time window there will always be a mismatch between the number of data units received and the number of data pairs which can be created. This implies that the slower clock source dominates the rate at which data pairs can be created and requires the data interleaving system to have memory to store the excess data coming from the faster data stream.
Under continuous data interleaving operation, the interleaving system would have to have an infinite memory depth because it must continuously store the faster system's excess data. However, if a finite limit can be imposed on the size of the data expected, then the interleaving system only requires a memory which is deep enough to hold the excess data which accumulates over the transmission time of the data stream. Upon completing the transmission of the frame data from both asynchronous input data streams, some idle time is required to transmit the excess data from the faster data stream. The idle time between data stream transmissions must be long enough for the interleaving system to empty the memory where the excess data has accumulated. Only when these two conditions are met, 1) finite amount of data and 2) sufficient idle time between data stream transmissions, can a system be developed to handle the interleaving of two or more asynchronous data streams.
One application of this method is described below where image data from two asynchronous image acquisition systems of a duplex scanner are to be merged. For the remainder of this disclosure, the preferred embodiment will be limited to a duplex scanner where the front and rear side images of a document are to be merged using a raster interleaving technique. The reader is reminded that pixel interleaving and document interleaving are also possible, both of which are variations of raster interleaving.
In the past, applications which required interleaving of multiple asynchronous data streams typically employed techniques which involved significant processing resources and/or significant memory resources. The asynchronous nature of the incoming data dramatically increased the complexity of the interleaving process. Typically, the methods employed required that the data streams be synchronous to one another. For example, one method might implement a master clock on one data acquisition system while the other data acquisition system is synchronized to the master via a phase locking mechanism. From a manufacturing perspective, this required that both a master and a slave data acquisition system be stocked, in addition to the phase locking implementation. This had the advantage of both increased system complexity and increased system cost. Furthermore, group delays associated with transmitting the master clock between systems would cause a skew between the data and clock of the slave system. This is especially true, and a potential limitation, at high data rates or while transmitting data over long distances.
Another scheme for merging data from multiple sources is to have a master clock at the receiver. This master clock is then transmitted to the data acquisition systems. Once again, this scheme presents a problem with group delays which would cause skew between the data and the clock, possibly limiting data rates and transmission distances. Furthermore, the clock frequency of the image acquisition systems in this scenario is dictated by the data receiver making the system less flexible.
Earlier methods of interleaving data, such as that disclosed in U.S. Pat. No. 5,398,241, "High Speed Asynchronous Multiplexer Demultiplexer," require significant amounts of data storage, and also require the use of overhead data to allow for proper synchronization of the data. Furthermore, the particular method described in U.S. Pat. No. 5,398,241 requires sophisticated and costly logic to generate a variable rate output signal. These drawbacks cause decreased efficiency of the data processing, and cause increased cost in the apparatus required to acquire and process such data.
With regard to the preferred embodiment, traditional methods of scanning and processing both sides of a two-sided document suffer from such problems as slow copying (due to the need to pass the documents through the same copying mechanism twice), or increased cost (due to having two sets of image processors in order to copy both sides.) Furthermore, none of the prior art methods involve simultaneously copying both sides of a document using only one image processing engine.
The method according to the present invention allows data from asynchronous data sources to be properly interleaved without implementation of complex phase or frequency compensation techniques (such as phase locked loops), and with a minimized amount of data storage for buffering the input data. Optimization of the data processing occurs as a result of the low overhead, and costs are reduced as a result of the reduced memory requirements over traditional approaches for this type of data acquisition.
With reference to the preferred embodiment, the current invention alleviates the need to pass a document through the copying mechanism more than once. Instead, the document passes only once through an apparatus practicing the current invention, and thus the image processing engine must only process the input data once. This results in a significant reduction in costs associated with the image processing functionality, increased reliability, lower power requirements, and a more compact design. In addition, with only a single image processing system, fewer parts need to be stocked by the various manufacturing and service organizations.